#include <stdio.h>

// #define MIN(a,b) {(a < b)? a:b}
// // 列扫描法，通过
// int trap(int* height, int heightSize){
//     int sum = 0;

//     for (int i = 1; i < heightSize-1; i++) {
//         int left_max = 0;   //左边最高
//         for (int j = i-1; j >= 0; j--) {
//             if (height[j] > left_max)
//                 left_max = height[j];
//         }

//         int right_max = 0;   //右边最高
//         for (int j = i+1; j < heightSize; j++) {
//             if (height[j] > right_max)
//                 right_max = height[j];
//         }
//         //较小的一端
//         int min = MIN(left_max, right_max);
//         if (min > height[i])
//             sum += (min - height[i]);
//     }
//     return sum;
// }


// #define MIN(a,b) ((a < b)? a:b)
// #define MAX(a,b) ((a > b)? a:b)
// // 列扫描法 + 动态规划，通过
// int trap(int* height, int heightSize){
//     int i, sum = 0;
//     if (heightSize == 0) return 0;
//     //保存中间所有列，左右端的最高墙壁
//     int left_max[heightSize], right_max[heightSize];    
//     memset(left_max, 0 , sizeof(int)*heightSize);
//     memset(right_max, 0 , sizeof(int)*heightSize);

//     for (i = 1; i < heightSize-1; i++) {
//         left_max[i] = MAX(left_max[i-1], height[i-1]);
//     }
//     for (i = heightSize-2; i >= 1; i--) {
//         right_max[i] = MAX(right_max[i+1], height[i+1]);
//     }

    
//     for (int i = 1; i < heightSize-1; i++) {
//         //较小的一端
//         int min = MIN(left_max[i], right_max[i]);
//         if (min > height[i])
//             sum += (min - height[i]);
//     }
//     return sum;
// }

// 双指针法，通过
int trap(int* height, int heightSize){
    int sum = 0;
    if (heightSize == 0) return 0;
    int min, lbound = height[0], rbound = height[heightSize-1];
    int l = 1, r = heightSize-2;
    while (l <= r) {
       if (lbound <= rbound) { 
           min = lbound;  
           if (height[l] < min) {
                sum += (min - height[l]);
            } else {    //更新左边界
                lbound = height[l];
            }
            l++;
        } else {
            min = rbound;  
            if (height[r] < min) {
                sum += (min - height[r]);
            } else {    //更新左边界
                rbound = height[r];
            }
            r--;
        }
    }
    return sum;
}

int main()
{
	int arr[] = {2,0,2};
	printf("%d\n",trap(arr,3));
	return 0;
}

// 可用单调减栈做此题，思想同柱状图中的最大矩形
